package com.lishem.leftgod.level1.class02;

/**
 * 在给定的原字符串 str 后添加字符使得到的新字符串包含两个原字符串，要求添加的字符是最少的
 */
public class Code_02_KMP_ShortestHaveTwice {


    public static String answer(String str) {
        if (str == null || str.length() == 0) {
            return "";
        }
        char[] ms = str.toCharArray();
        int index = getNext(ms);
        System.out.println(index);
        return str + str.substring(index);
    }

    private static int getNext(char[] ms) {
        if (ms.length == 1) {
            return 0;
        }
        int[] next = new int[ms.length + 1];
        next[0] = -1;
        next[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos != next.length) {
            if (ms[pos - 1] == ms[cn]) {
                next[pos++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[pos++] = 0;
            }
        }
        return next[ms.length];
    }

    public static void main(String[] args) {
//        String test1 = "a";
//        System.out.println(answer(test1));
//
//        String test2 = "aa";
//        System.out.println(answer(test2));
////
//        String test3 = "ab";
//        System.out.println(answer(test3));

        String test4 = "abcdabcd";
        System.out.println(answer(test4));

        String test5 = "abracadabra";
        System.out.println(answer(test5));

    }


}
